#include <vector>
#include <assert.h>

class MergeSort
{
private:
    /* data */
public:
    // static void sort(std::vector<int>& nums)
    // {
    //     static MergeSort solution;
    //     solution.MergeSort(nums, 0, nums.size()-1);
    // }

    void mergeSort(std::vector<int>& nums, int left, int right)
    {
        if (left == right) return;
        int mid = left + (right-left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        merge(nums, left, mid+1, right);
    }

    void merge(std::vector<int>& nums, int leftPtr, int rightPtr, int rightBound)
    {
        int mid = rightPtr - 1;
        std::vector<int> temp(rightBound-leftPtr+1);
        int i = leftPtr;
        int j = rightPtr;
        int k = 0;

        while (i <= mid && j <= rightBound) temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= rightBound) temp[k++] = nums[j++];
        for (int m = 0; m < temp.size(); m++) nums[leftPtr+m] = temp[m];
    }
};


int main() 
{
    std::vector<int> nums = {1,3,5,2,7,8,9,4,6,0};
    MergeSort s;
    s.mergeSort(nums, 0, nums.size()-1);
    for (int i = 0; i < nums.size(); i++) {
        assert(nums[i]==i);
    }
}
